/**
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  let l = nums.length;
  let final = [];
  let resultMap = {};
  if (l < 3) {
    return []
  }
  let i, j;
  let zeroGroup = [];
  let leftGroup = [];
  let rightGroup = [];
  // 往数组中放一个0，便于分组
  nums.push(0);
  nums = nums.sort(function (a, b) {
    return a - b
  });
  // 把数组分成三部分，负数，0，正数
  let zeroIndex = splitNums(nums, 0, nums.length, 0);
  // 判断有多个0的情况
  for (i = zeroIndex; i >= 0; i--) {
    const element = nums[i];
    if (element === 0) {
      continue;
    }
    i++;
    break;
  }
  for (j = zeroIndex; j <= l; j++) {
    const element = nums[j];
    if (element === 0) {
      continue;
    }
    j--;
    break;
  }
  console.log(i, j, nums)
  if (i >= 0) {
    leftGroup = nums.slice(0, i);
  } else {
    i = 0;
  }
  rightGroup = nums.slice(j + 1);
  zeroGroup = nums.slice(i, j + 1);
  nums.splice(zeroIndex, 1);
  zeroGroup.pop();
  let li = leftGroup.length;
  let zi = zeroGroup.length;
  let ri = rightGroup.length;
  console.log(zeroGroup, leftGroup, rightGroup)
  let maxSize = Math.max(Math.abs(nums[0]), nums[nums.length - 1]);
  for (i = 0; i <= maxSize; i++) {
    let targetIndex = rightGroup.indexOf(i);
    // 原数组内没有0
    if (i === 0 && zi === 0) {
      continue;
    }
    // 数没有在数组内
    if (i != 0 && targetIndex === -1) {
      continue;
    }
    for (j = 0; j < l; j++) {
      const value = nums[j];
      if (value === i && j === (li + zi + targetIndex)) {
        console.log('同一个数', value)
        continue;
      }
      if (i === 0 && value === 0 && zi < 3) {
        continue;
      }
      console.log(value, i);
      // 计算差值
      let diff = 0 - (value + i);
      let has = false;
      // 判断差值是否在名单内
      if (diff < 0) {
        has = leftGroup.indexOf(diff);
      } else if (diff > 0) {
        has = rightGroup.indexOf(diff);
        if (targetIndex === has) {
          // 匹配到自己了
          has = -1;
        }
      } else {
        has = zeroGroup.indexOf(diff);
      }
      // 不是自己
      if (has !== -1 && has !== j) {
        let sorted = [diff, i, value].sort();
        if (!resultMap[sorted.join('|')]) {
          final.push([diff, i, value]);
          resultMap[sorted.join('|')] = true;
        }
      }
    }
  }
  return final;
};

function splitNums(nums, start, end, target) {
  if (start > end) {
    return -1;
  }
  let middle = parseInt((start + end) / 2);
  if (typeof nums[middle] === undefined) {
    return -1;
  }
  if (nums[middle] > target) {
    return splitNums(nums, start, middle - 1, target);
  }
  if (nums[middle] < target) {
    return splitNums(nums, middle + 1, end, target);
  }
  return middle;
}

console.log(threeSum([-1,0,1,2,-1,-4,-2,-3,3,0,4]))
// console.log(threeSum([-1,0,1,2,-1,-4]));
// console.log(threeSum([-1, -1, -1, 1]));
// console.log(threeSum([1,2,3,4]));
// console.log();
// var arr = [-4,-3,-2,-1, 1,2,3,4,5];
// arr.push(0);
// console.log(splitNums(arr, 0, 9, 5))